package com.unbiz.common.algorithms;

import static java.util.stream.Collectors.toList;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Optional;
import java.util.function.Function;
import java.util.stream.Stream;



/**
 * Represents one node of a tree. A node can either be a leaf or a joint
 * between nodes.
 *
 * @param <T> The type of data maintained by this node and its children.
 */
public final class Node<T> {

    T data;
    Node<T> parent;
    final List<Node<T>> children = new LinkedList<>();

    public Node(T data) {
        this.data = data;
    }

    /**
     * Gets the data associated with a node.
     *
     * @return The node's data.
     */
    public final T getData() {
        return data;
    }

    /**
     * Set the data associated with a node.
     *
     * @param data The data to set onto the node.
     */
    public final void setData(T data) {
        this.data = data;
    }

    /**
     * Get an optional of this node's parent, if any.
     *
     * @return An optional containing the parent node of this node, if any.
     */
    public final Optional<Node<T>> getParent() {
        return Optional.ofNullable(parent);
    }

    /**
     * Get an unmodifiable list of this nodes children.
     * If you need to add children, use the "addChildren" methods.
     *
     * @return The list of child nodes.
     */
    public final List<Node<T>> getChildren() {
        return Collections.unmodifiableList(children);
    }

    /**
     * Get all the siblings of this node.
     *
     * @return The list of sibling nodes.
     */
    public final List<Node<T>> getSiblings() {
        return getParent().map(parent -> parent.getChildren().stream()
                .filter(node -> node != this))
                .orElse(Stream.empty()).collect(toList());
    }

    public final Node<T> addChild(T data) {
        Node<T> child = new Node<>(data);
        children.add(child);
        child.parent = this;
        return this;
    }

    public final Node<T> addChildNode(Node<T> child) {
        children.add(child);
        child.parent = this;
        return this;
    }

    @SafeVarargs
    public final Node<T> addChildren(T... data) {
        Arrays.stream(data).map((Function<T, Node<T>>) Node::new).map(child -> {
            child.parent = this;
            return child;
        }).forEachOrdered(children::add);
        return this;
    }

    @SafeVarargs
    public final Node<T> addChildrenNodes(Node<T>... data) {
        Arrays.stream(data).map(child -> {
            child.parent = this;
            return child;
        }).forEachOrdered(children::add);
        return this;
    }

    public final Node<T> addChildren(Collection<T> data) {
        data.stream().map((Function<T, Node<T>>) Node::new).map(child -> {
            child.parent = this;
            return child;
        }).forEachOrdered(children::add);
        return this;
    }

    public final Node<T> addChildrenNodes(Collection<Node<T>> data) {
        data.stream().map(child -> {
            child.parent = this;
            return child;
        }).forEachOrdered(children::add);
        return this;
    }

    /**
     * Gets a new tree with this acting as the root.
     * Note that the root node of the new tree will
     * be parentless even if this node has a parent.
     * This is important for the recursive operations
     * for determining depth and order. This node instance
     * and all of its children will go unmodified because
     * an entire structural copy is made.
     *
     * @return A tree view of a structural clone. Any
     *         structural changes made on the new tree
     *         will not impact the structure to which this
     *         node currently belongs. Any changes to a nodes
     *         data *can* impact the data contained in this instances
     *         nodes. If you need a complete (deep) clone, then please
     *         call the deep clone function on the new tree along with
     *         a function describing how to clone each piece of data in
     *         the tree.
     */
    public final Tree<T> asTree() {
        return new Tree<T>(this, true);
    }

    /**
     * Gets the root node of the current structure by traversing up
     * the chain of parents. If a node has no parent, then that node
     * will be returned.
     *
     * @return The root node of the current tree structure of which
     *         this node is a part.
     */
    public final Node<T> getRootOfTree() {
        return getParent().map(Node::getRootOfTree).orElse(this);
    }

    /**
     * Gets the depth within the tree at which this node lives.
     * Depth is zero indexed, meaning that the depth of the root
     * node is 0.
     *
     * @return The depth.
     */
    public final int getDepth() {
        return getParent().map(parent -> parent.getDepth() + 1).orElse(0);
    }

    /**
     * Gets the degree of this node (the number of outbound edges).
     *
     * @return The number of outbound edges (eq to the number of children).
     */
    public final int getDegree() {
        return getChildren().size();
    }

    /**
     * Gets the global order within the tree at which this node lives.
     * Global order is determined by how far (from left to right) this
     * node lives amongst other nodes at the same depth. Order is zero
     * indexed meaning that left-most nodes for any depth have a global
     * order of 0.
     *
     * @return The global order.
     */
    public final int getGlobalOrder() {
        return Tree.indexOfByRef(new Tree<>(getRootOfTree(), false)
                .getDepthAsNodes(getDepth())
                .collect(toList()), this);
    }

    /**
     * Gets the local order within the tree at which this node lives.
     * Local order is determined by how far (from left to right) this
     * node lives amongst its siblings (underneath its parent). Order is zero
     * indexed meaning that left-most nodes under a parent have a local
     * index of 0.
     *
     * @return The local order.
     */
    public final int getLocalOrder() {
        return getParent().map(Node::getChildren)
                .map(list -> Tree.indexOfByRef(list, this))
                .orElse(0);
    }

    /**
     * Filters this node out of the tree context in which it is in.
     * filtering out a node means transferring all of its children
     * to be siblings of itself and then removing itself from its
     * parent.
     */
    void filter() {
        getParent().ifPresent(parent -> {
            parent.addChildrenNodes(this.getChildren());
            parent.children.remove(this);
        });
    }

    /**
     * Prunes this node out of the tree context in which it is in.
     * Pruning out a node means removing it and, by extension, all
     * of its children.
     */
    void prune() {
        getParent().ifPresent(parent -> parent.children.remove(this));
    }

    <S> Node<S> map(Function<T, S> func) {
        return mapAsNode(n -> func.apply(n.getData()));
    }

    <S> Node<S> flatMap(Function<T, Node<S>> func) {
        return flatMapAsNode(n -> func.apply(n.getData()));
    }

    <S> Node<S> mapAsNode(Function<Node<T>, S> func) {
        Node<S> node = new Node<>(func.apply(this));
        children.stream().map(child -> child.mapAsNode(func))
                .forEachOrdered(node::addChildNode);
        return node;
    }

    <S> Node<S> flatMapAsNode(Function<Node<T>, Node<S>> func) {
        Node<S> node = func.apply(this);
        children.stream().map(child -> child.flatMapAsNode(func))
                .forEachOrdered(node::addChildNode);
        return node;
    }

    Stream<Node<T>> getAncestry() {
        return getParent().map(parent -> Stream.concat(parent.getAncestry(), Stream.of(parent)))
                .orElse(Stream.empty());
    }

    @Override
    public final boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof Node)) {
            return false;
        }
        Node<?> treeNode = (Node<?>) o;
        return Objects.equals(data, treeNode.data);
    }

    @Override
    public final int hashCode() {
        return Objects.hash(data);
    }

    @Override
    public final String toString() {
        return Objects.toString(data);
    }

}